package a_doubleWrite;

import java.util.Arrays;

/**
 * 计数质数
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-07-30 09:36
 */
public class L204 {
    public int countPrimes(int n) {
        //埃氏筛
        int[] nums = new int[n];
        Arrays.fill(nums, 1);
        for (int i = 2; i < n; i++) {
            if (nums[i] == 1) {
                //将该数的倍数，置为0
                for (int j = i * i; j <= n; j += i) {
                    nums[j] = 0;
                }
            }
        }
        int ans = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i] == 1) ans++;
        }
        return ans;
    }

    public static void main(String[] args) {
        L204 l204 = new L204();
        int i = l204.countPrimes(11);
        System.out.println(i);
    }
}
